11088 - End up with more teams/11088.cpp

   1 /*
   2   Problem: 11088 - End up with More Teams
   3   Author: Andrés Mejía-Posada
   4   (http://blogaritmo.factorcomun.org)
   5
   6   Accepted
   7  */
   8
   9 #include <algorithm>
  10 #include <iostream>
  11 #include <iterator>
  12 #include <sstream>
  13 #include <fstream>
  14 #include <cassert>
  15 #include <climits>
  16 #include <cstdlib>
  17 #include <cstring>
  18 #include <string>
  19 #include <cstdio>
  20 #include <vector>
  21 #include <cmath>
  22 #include <queue>
  23 #include <deque>
  24 #include <stack>
  25 #include <map>
  26 #include <set>
  27 using namespace std;
  28
  29 #define D(x) cout << #x " is " << x << endl
  30 #define bit(i, n) (n & (1 << i))
  31
  32 int memo[1<<15], x[15], n;
  33
  34 /*
  35   Returns the maximum amount of teams that can be made using
  36   teams set on on bitwise mask avail. At each step, I try to
  37   build a new team using the first available person, or igno-
  38   re that person completely.
  39  */
  40 int best(int avail){
  41   int &ans = memo[avail];
  42   if (ans == -1){
  43     ans = 0;
  44     for (int i=0; i<n; ++i)
  45       if (bit(i, avail)){
  46         ans = max(ans, best(avail & ~(1 << i))); //Ignore this dogg
  47         for (int j=i+1; j<n; ++j)
  48           if (bit(j, avail))
  49             for (int k=j+1; k<n; ++k)
  50               if (bit(k, avail))
  51                 if(x[i] + x[j] + x[k] >= 20)
  52                   ans = max(ans, 1 + best(avail & ~(1 << i) & ~(1 << j) & ~(1 << k))); //Make team (i, j, k).
  53         break;
  54       }
  55   }
  56   //printf("best(%X) = %d\n", avail, ans);
  57   return ans;
  58 }
  59
  60 int main(){
  61   int pizza = 1;
  62   while (scanf("%d", &n) == 1 && n){
  63     for (int i = 0; i<n; ++i) scanf("%d", &x[i]);
  64
  65     memset(memo, -1, sizeof memo);
  66     printf("Case %d: %d\n", pizza++, best((1 << n) - 1));
  67   }
  68
  69   return 0;
  70 }